#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define MAX_TREES 3 // 森林中树的最大数量

// 孩子兄弟表示法结点结构
typedef struct CSNode
{
    int data;                   // 结点数据
    struct CSNode *firstChild;  // 指向第一个孩子
    struct CSNode *nextSibling; // 指向右兄弟
} CSNode, *CSTree;

// 森林结构（包含三棵树）
typedef struct
{
    CSTree trees[MAX_TREES]; // 树根结点指针数组
    int treeCount;           // 当前树的数量
} Forest;

// 1. 初始森林
void InitForest(Forest &F)
{
    F.treeCount = 0;
    for (int i = 0; i < MAX_TREES; i++)
    {
        F.trees[i] = NULL; // 所有树根指针置空
    }
}

// 2. 销毁单棵树（递归）
void DestroyTree(CSTree &T)
{
    if (T)
    {
        DestroyTree(T->firstChild);  // 销毁子树
        DestroyTree(T->nextSibling); // 销毁兄弟树
        free(T);                     // 释放当前结点
        T = NULL;
    }
}

// 3. 销毁森林（递归释放所有结点）
void DestroyForest(Forest &F)
{
    for (int i = 0; i < F.treeCount; i++)
    {
        if (F.trees[i])
        {
            // 递归销毁树
            DestroyTree(F.trees[i]);
            F.trees[i] = NULL;
        }
    }
    F.treeCount = 0;
}

// 4. 插入结点（重点检查部分）
bool InsertNode(CSTree &parent, int value, bool asFirstChild)
{
    // 创建新结点
    CSNode *newNode = (CSNode *)malloc(sizeof(CSNode));
    if (!newNode)
    {
        printf("Error: Memory allocation failed\n");
        return false;
    }

    newNode->data = value;
    newNode->firstChild = NULL;
    newNode->nextSibling = NULL;

    // 作为第一个孩子插入
    if (asFirstChild)
    {
        // 新结点接管原第一个孩子作为兄弟
        newNode->nextSibling = parent->firstChild;
        parent->firstChild = newNode;
    }
    // 作为兄弟插入
    else
    {
        // 找到最后一个兄弟
        CSNode *sibling = parent->firstChild;
        if (!sibling)
        {
            // 没有孩子则不能插入兄弟
            free(newNode);
            printf("Error: Parent has no children, cannot insert as sibling\n");
            return false;
        }

        while (sibling->nextSibling)
        {
            sibling = sibling->nextSibling;
        }
        sibling->nextSibling = newNode;
    }
    return true;
}

// 5.1 先根遍历（递归）
void PreOrder(CSTree T)
{
    if (T)
    {
        printf("%d ", T->data);   // 访问当前结点
        PreOrder(T->firstChild);  // 遍历子树
        PreOrder(T->nextSibling); // 遍历兄弟树
    }
}

// 5.2 后根遍历（递归）
void PostOrder(CSTree T)
{
    if (T)
    {
        PostOrder(T->firstChild);  // 先遍历子树
        printf("%d ", T->data);    // 后访问当前结点
        PostOrder(T->nextSibling); // 最后遍历兄弟树
    }
}

// 5.3 层序遍历（队列实现）
void LevelOrder(CSTree T)
{
    if (!T)
        return;

    CSTree queue[100];
    int front = 0, rear = 0;
    queue[rear++] = T; // 根结点入队

    while (front < rear)
    {
        CSTree node = queue[front++];
        printf("%d ", node->data); // 访问结点

        // 所有孩子入队
        if (node->firstChild)
        {
            CSTree child = node->firstChild;
            queue[rear++] = child;

            // 所有兄弟入队
            while (child->nextSibling)
            {
                child = child->nextSibling;
                queue[rear++] = child;
            }
        }
    }
}

// 5.4 森林遍历
void TraverseForest(Forest F, const char *order)
{
    for (int i = 0; i < F.treeCount; i++)
    {
        if (!F.trees[i])
            continue;

        printf("Tree %d: ", i + 1);

        if (strcmp(order, "preorder") == 0)
        {
            PreOrder(F.trees[i]);
        }
        else if (strcmp(order, "postorder") == 0)
        {
            PostOrder(F.trees[i]);
        }
        else if (strcmp(order, "levelorder") == 0)
        {
            LevelOrder(F.trees[i]);
        }
        printf("\n");
    }
}

int main()
{
    Forest F;
    InitForest(F);
    F.treeCount = 3; // 三棵树

    // 创建根结点
    for (int i = 0; i < MAX_TREES; i++)
    {
        F.trees[i] = (CSTree)malloc(sizeof(CSNode));
        F.trees[i]->data = i * 3 + 1; // 1, 4, 7
        F.trees[i]->firstChild = NULL;
        F.trees[i]->nextSibling = NULL;
    }

    // 构建第一棵树 (1为根，2为左孩子，3为右孩子)
    InsertNode(F.trees[0], 2, true);  // 第一个孩子
    InsertNode(F.trees[0], 3, false); // 作为兄弟插入

    // 构建第二棵树 (4为根，5为左孩子，6为右孩子)
    InsertNode(F.trees[1], 5, true);  // 第一个孩子
    InsertNode(F.trees[1], 6, false); // 作为兄弟插入

    // 构建第三棵树 (7为根，8为左孩子，9为右孩子)
    InsertNode(F.trees[2], 8, true);  // 第一个孩子
    InsertNode(F.trees[2], 9, false); // 作为兄弟插入

    // 遍历测试
    printf("Forest preorder traversal:\n");
    TraverseForest(F, "preorder");

    printf("\nForest postorder traversal:\n");
    TraverseForest(F, "postorder");

    printf("\nForest levelorder traversal:\n");
    TraverseForest(F, "levelorder");

    // 销毁森林
    DestroyForest(F);
    printf("\nForest destroyed\n");

    return 0;
}